;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname |4|) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ())))
(require rackunit)

;; Program for a robot that moves on a 20X20 chessboard starting at (1,1) and
;; the robot, at start, is placed at (1,1) facing East.

;; ALGORITHM:
;; 1. check if the given S-expression represents a valid command by
;;    checking for all possible combinations of symbols (that represent valid commands) 
;;    and the associated arguments needed.
;; 2. if the S-expression is found to be an invalid representation of command
;;    the return false.
;; 3. if the S-expression is found to be a valid representation of command
;;    then convert the S-expression to the internal syntax, traversing through
;;    whole of the S-expression and converting each part to a corresponding
;;    internal syntax command in the following manner.
;;    . the arguments needed by each command are clubbed together to form
;;       a command in internal syntax.
;;    
;;;;;;;;;;;;;;;;;;;;;;;;;;Data Definitions;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; NonNegInt represents any non-negative interger.

(define-struct forward (n))
;; Forward is a (make-forward NonNegInt)
;; Interp: internal syntax of a command that moves the robot forward in the current direction
;; -- n  : a non-negative integer that represents the number of blocks by which 
;;         the robot is supposed to move forward on the chessboard
;; INVARIANT: the robot moves forward by the number of blocks given by 
;;            minimum of n and (number of forward moves required to reach the
;;            edge in the current direction)

(define-struct backward (n))
;; Backward is a (make-backward NonNegInt)
;; Interp: internal syntax of a command that moves the robot backward in the current direction
;; -- n  : a non-negative integer that represents the number of blocks by which 
;;         the robot is supposed to move backward on the chessboard
;; INVARIANT: the robot moves backward by the number of blocks given by 
;;            minimum of n and (number of backward moves required to reach the
;;            edge in the opposite direction)

(define-struct left ())
;; Left is a (make-left)
;; Interp: internal syntax of a command that turns the robot 90 degrees counterclockwise

(define-struct right ())
;; Right is a (make-right)
;; Interp: command that turns the robot 90 degrees clockwise

(define-struct do-times (n cmd))
;; Do-times is a (make-do-times NonNegInt Cmd)
;; Interp: internal syntax of a command that executes the given command by the given number of times
;; -- n   : a non-negative integer that represents the number of times the given
;;          command is to be executed
;; -- cmd : the command in internal syntax Cmd that needs to be executed 

(define-struct if-at-edge (cmd1 cmd2))
;; If-at-edge is a (make-if-at-edge Cmd Cmd)
;; Interp: internal syntax of a command that executes the given command cmd1 if the robot faces an 
;;         edge else executes the given command cmd2
;; -- cmd1 : the command in internal syntax Cmd that needs to be executed
;;           if the robot faces an edge
;; -- cmd2 : the command in internal syntax Cmd that needs to be executed 
;;           if the robot is not at edge 

(define-struct while-not-at-edge (cmd))
;; While-not-at-edge is a (make-while-not-at-edge Cmd)
;; Interp: internal syntax of a command that keeps executing the given command while the robot 
;;         is not facing an edge.
;; -- cmd : the command in internal syntax Cmd that needs to be executed

;; Location is a (list Number Number Direction)
;; Interp: the location of the robot on the chessboard that is represented by 
;;         the position (i j) and the direction in which the robot is facing.
;;         location is represented as list of three elements, i and j coordinates 
;;         and the direction. position (i j) represents row i and column j on the 
;;         chessboard and each is a number greater than or equal to 1 and 
;;         less than or equal to 20.
;;
;; Template:
;; location-fn : Location -> ??
;(define (location-fn loc)
;  (... (first loc) (second loc) (third loc)))

(define-struct result (location moves))
;; A Result is a (make-result Location ListOf<Move>)
;; Interp: the result after a command is interpreted and executed
;; location : the location of the robot on the chessboard
;; moves    : the moves that have been applied on the robot
;;            
;; Template:
;; result-fn : Result -> ??
;(define (result-fn res)
;  (... (result-location res)
;       (result-moves res)))

;; A Direction is a Symbol 
;; which represents the direction in which the robot is facing,
;; and is either
;; -- 'north
;;    Interp: direction North
;; -- 'east
;;    Interp: direction East
;; -- 'south
;;    Interp: direction South
;; -- 'west
;;    Interp: direction West
;;
;; Template:
;; direction-fn : Direction -> ??
;(define (direction-fn dir)
;  (cond
;    [(symbol=? dir 'north) ...]
;    [(symbol=? dir 'east) ...]
;    [(symbol=? dir 'south) ...]
;    [(symbol=? dir 'west) ...]))

;; A Move is a Symbol
;; which represents the move applied on the robot,
;; and is either
;; -- 'forward
;; Interp: move corresponding to the forward command
;; -- 'backward
;; Interp: move corresponding to the backward command
;; -- 'left
;; Interp: move corresponding to the left command
;; -- 'right
;; Interp: move corresponding to the right command
;;
;; Template
;; move-fn : Move -> ??
;(define (move-fn move)
;  (cond
;    [(symbol=? move 'forward) ...]
;    [(symbol=? move 'backward) ...]
;    [(symbol=? move 'left) ...]
;    [(symbol=? move 'right) ...]))

;; ListOf<Move> is either
;; -- empty
;;    Interp: no move
;; -- (cons Move ListOf<Move>)
;;    Interp: a list of moves that correspond to the commands
;;            forward, backward, left and right.

;; An AtomicSymbol is either
;; -- Number
;;    Interp: a number 
;; -- Symbol
;;    Interp: a symbol
;;
;; A SexpOf<AtomicSymbol> is either
;; -- empty
;;    Interp: no element
;; -- AtomicSymbol
;;    Interp: an AtomicSymbol
;; -- (cons AtomicSymbol SexpOf<AtomicSymbol>)
;;    Interp: a list of AtomicSymbol and nested list of AtomicSymbol
;;    (that cannot be just an AtomicSymbol)
;; -- (cons (cons AtomicSymbol SexpOf<AtomicSymbol>) SexpOf<AtomicSymbol>)
;;    Interp: a list of following
;;    1. list of AtomicSymbol and nested list of AtomicSymbol
;;       (that cannot be just an AtomicSymbol)
;;    2. nested list of AtomicSymbol (that cannot be just an AtomicSymbol)
;;
;; Template:
;; sexpas-fn : SexpOf<AtomicSymbol> -> ??
;(define (sexpas-fn sexp-as)
;  (cond [(empty? sexp-as) ...]
;        [(or (number? sexp-as) 
;             (symbol? sexp-as))
;         ... ]
;        [(or (number? (first sexp-as) 
;             (symbol? (first sexp-as))
;         ... ]
;        [else ... (first (first sexp-as))
;                  (sexpas-fn (rest (first sexp-as)))
;              (sexpas-fn (rest sexp-as))]))

;; An ExtCmd is the valid representation of the external syntax
;; of command and is either
;; -- SequenceExtCmd
;;    Interp: a SequenceExtCmd representing a sequence of commands
;; -- (list 'forward NonNegInt)
;;    Interp: a list of two elements, symbol forward and 
;;    a non-negative Integer
;; -- (list 'backward NonNegInt)
;;    Interp: a list of two elements, symbol backward and
;;    a non-negative Integer 
;; -- (list 'left)
;;    Interp: a list of one element, symbol left
;; -- (list 'right)
;;    Interp: a list of one element, symbol left
;; -- (list 'do-times NonNegInt ExtCmd)
;;    Interp: a list of three elements, symbol do-times, a
;;    non-negative Integer and an ExtCmd
;; -- (list 'if-at-edge ExtCmd ExtCmd)
;;    Interp: a list of three elements, symbol if-at-edge,
;;    and two ExtCmd
;; -- (list 'while-not-at-edge ExtCmd)
;;    Interp: a list of two elements, symbol while-not-at-edge,
;;    and an ExtCmd
;;
;; Template:
;; ext-cmd-fn : ExtCmd -> ??
;(define (ext-cmd-fn ext-cmd)
;  (cond 
;    [(or (empty? ext-cmd) 
;         (cons? (first ext-cmd))) (seq-ext-cmd-fn ext-cmd)]
;    [(symbol=? (first ext-cmd) 'forward) 
;     ... (second ext-cmd)]
;    [(symbol=? (first ext-cmd) 'backward)
;     ... (second ext-cmd)]
;    [(symbol=? (first ext-cmd) 'left)
;     ... ]
;    [(symbol=? (first ext-cmd) 'right) 
;     ... ]
;    [(symbol=? (first ext-cmd) 'do-times) 
;     ... (second ext-cmd) (ext-cmd-fn (third ext-cmd))]
;    [(symbol=? (first ext-cmd) 'if-at-edge) 
;     ... (ext-cmd-fn (second ext-cmd))
;         (ext-cmd-fn (third ext-cmd))]
;    [(symbol=? (first ext-cmd) 'while-not-at-edge)
;     ... (ext-cmd-fn (second ext-cmd))]))

;; A SequenceExtCmd is either
;; -- empty
;;    Interp: no element
;; -- (cons ExtCmd SequenceExtCmd)
;;    Interp: a list of ExtCmd
;;
;; Template:
;; seq-ext-cmd-fn : SequenceExtCmd -> ??
;(define (seq-ext-cmd-fn lst)
;  (cond 
;    [(empty? lst) ...]
;    [else ... (ext-cmd-fn (first lst)) 
;          (seq-ext-cmd-fn (rest lst))]))

;; A UnitCmd is either
;; -- Forward
;;    Interp: internal syntax of forward command
;; -- Backward
;;    Interp: internal syntax of backward command
;; -- Left
;;    Interp: internal syntax of left command
;; -- Right
;;    Interp: internal syntax of right command
;; -- Do-times
;;    Interp: internal syntax of do-times command
;; -- If-at-edge
;;    Interp: internal syntax of if-at-edge command
;; -- While-not-at-edge
;;    Interp: internal syntax of while-not-at-edge command
;;
;; Template:
;(define (unitcmd-fn unitcmd)
;  (cond 
;    [(forward? unitcmd) 
;     ... (forward-fn unitcmd)]
;    [(backward? unitcmd) 
;     ... (backward-fn unitcmd)] 
;    [(left? unitcmd) 
;     ... (left-fn unitcmd)] 
;    [(right? unitcmd) 
;     ... (right-fn unitcmd)]
;    [(do-times? unitcmd) 
;     ... (do-times-fn unitcmd)] 
;    [(if-at-edge? unitcmd) 
;     ... (if-at-edge? unitcmd)] 
;    [(while-not-at-edge? unitcmd) 
;     ... (while-not-at-edge-fn unitcmd)]))

;; Cmd is the internal syntax of command
;; and is either
;; -- empty
;;    Interp: no command
;; -- UnitCmd
;;    Interp: a unit command
;; -- (cons UnitCmd Cmd)
;;    Interp: a list of unit commands representing
;;    a sequence command
;;
;; Template:
;(define (cmd-fn cmd)
;  (cond 
;       [(empty? cmd) ...]
;       [(struct? cmd) ...]
;       [else ...(unitcmd-fn (first cmd)) (cmd-fn (rest cmd))]))

;; Maybe<Cmd> is either
;; -- false
;;    Interp: false when SexpOf<AtomicSymbol> is not a valid 
;;    representation of command
;; -- Cmd
;;    Interp: internal syntax of valid command
;;
;; Template:
;; maybecmd-fn : Maybe<Cmd> -> ??
;(define (maybecmd-fn maybecmd)
;  (cond
;    [(boolean? maybecmd) ...]
;    [else ... (cmd-fn maybecmd)]))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;End of Data Definitions;;;;;;;;;;;;;;;;;;;;;;

;; decode : SexpOf<AtomicSymbol> -> Maybe<Cmd>
;; takes an external syntax as a nested list of AtomicSymbol and returns a 
;; command in internal syntax if the given external syntax represents a valid 
;; command else returns false.
;; Examples: See tests below
;; Strategy: Structural Decomposition (Enumeration on is-sexpas-valid? [Boolean])
(define (decode sexp-as)
  (cond 
    [(is-sexpas-valid? sexp-as)
     (decode-ext-cmd sexp-as)]
    [else #f]))

;; decode-ext-cmd : ExtCmd -> Cmd
;; takes a valid external syntax and returns a command in internal syntax
;; Examples: See tests below
;; Strategy: Structural Decomposition [ExtCmd]
(define (decode-ext-cmd ext-cmd)
  (cond 
    [(or (empty? ext-cmd) 
         (cons? (first ext-cmd))) (decode-seq-ext-cmd ext-cmd)]
    [(symbol=? (first ext-cmd) 'forward) 
     (make-forward (second ext-cmd))]
    [(symbol=? (first ext-cmd) 'backward) 
     (make-backward (second ext-cmd))]
    [(symbol=? (first ext-cmd) 'left) 
     (make-left)]
    [(symbol=? (first ext-cmd) 'right) 
     (make-right)]
    [(symbol=? (first ext-cmd) 'do-times) 
     (make-do-times (second ext-cmd) 
                    (decode-ext-cmd (third ext-cmd)))]
    [(symbol=? (first ext-cmd) 'if-at-edge)
     (make-if-at-edge (decode-ext-cmd (second ext-cmd)) 
                      (decode-ext-cmd (third ext-cmd)))]
    [(symbol=? (first ext-cmd) 'while-not-at-edge) 
     (make-while-not-at-edge (decode-ext-cmd (second ext-cmd)))]))

;; decode-seq-ext-cmd : SequenceExtCmd -> Cmd
;; takes a valid external syntax of sequence command and returns a 
;; command in internal syntax
;; Examples: See tests below
;; Strategy: Structural Decomposition [SequenceExtCmd] using abstraction
(define (decode-seq-ext-cmd seq)
  (map decode-ext-cmd seq))

;; is-sexpas-valid? : SexpOf<AtomicSymbol> -> Boolean
;; takes an external syntax as a nested list of AtomicSymbol and returns true 
;; if the given external syntax represents a valid command else returns false.
;; Examples: See tests below
;; Strategy: Structural Decomposition [SexpOf<AtomicSymbol>]
(define (is-sexpas-valid? sexp-as)
  (cond [(empty? sexp-as) #t]
        [(or (number? sexp-as) 
             (symbol? sexp-as))
         #f]
        [(or (number? (first sexp-as)) 
             (symbol? (first sexp-as)))
         (is-valid? (first sexp-as) 
                    (rest sexp-as))]
        [else (and (is-valid? (first (first sexp-as)) 
                              (rest (first sexp-as)))
                   (is-sexpas-valid? (rest sexp-as)))]))

;; is-valid? : AtomicSymbol SexpOf<AtomicSymbol> -> Boolean
;; takes an atomic symbol and an external syntax as a nested list of AtomicSymbol, 
;; and returns true if the given atomic symbol and external syntax together represent 
;; a valid command else returns false.
;; Enumerates on the given atomic symbol and checks for valid combination with the
;; given nested list of AtomicSymbol and makes a decision whether the combination
;; is valid or not
;; Examples: See tests below
;; Strategy: Decision Tree
(define (is-valid? as sexp-as)
  (cond 
    [(number? as) #f]
    [(symbol=? as 'forward) 
     (and (not (empty? sexp-as))
          (number? (first sexp-as))
          (empty? (rest sexp-as)))]
    [(symbol=? as 'backward) 
     (and (not (empty? sexp-as))
          (number? (first sexp-as))
          (empty? (rest sexp-as)))]
    [(symbol=? as 'right) 
     (empty? sexp-as)]
    [(symbol=? as 'left) 
     (empty? sexp-as)]
    [(symbol=? as 'do-times) 
     (and (not (empty? sexp-as))
          (number? (first sexp-as))
          (not (empty? (rest sexp-as)))
          (cons? (second sexp-as))
          (empty? (rest (rest sexp-as)))
          (is-sexpas-valid? (second sexp-as)))]
    [(symbol=? as 'if-at-edge) 
     (and (not (empty? sexp-as))
          (cons? (first sexp-as))
          (is-sexpas-valid? (first sexp-as))
          (not (empty? (rest sexp-as)))
          (cons? (second sexp-as))
          (empty? (rest (rest sexp-as)))
          (is-sexpas-valid? (second sexp-as)))]
    [(symbol=? as 'while-not-at-edge) 
     (and (not (empty? sexp-as))
          (cons? (first sexp-as))
          (empty? (rest sexp-as))
          (is-sexpas-valid? (first sexp-as)))]
    [else #f]))

;;;;;;;;;;;;;;;;;;;;;;;;Tests for decode;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; test for empty S-expression
(check-equal?
 (decode empty)
 empty
 "given an empty S-expression, should return empty")

;; test for atomic symbol
(check-equal?
 (decode 'forward)
 #f
 "given an atomic symbol as S-expression, should return false")

;; test for a number 
(check-equal?
 (decode 3)
 #f
 "given a number, should return false")

;; test for a number 
(check-equal?
 (decode 3)
 #f
 "given a number, should return false")

;; test for a list containing a number 
(check-equal?
 (decode (list 3))
 #f
 "given a list containing a number, should return false")

;; test for a list containing an atomic symbol other than 
;; 'left and 'right
(check-equal?
 (decode (list 'forward))
 #f
 "given a list containing and atomic symbol other than 'left and 'right, 
  should return false")

;; test for a list containing a 'forward symbol and a non-negative integer
(check-equal?
 (decode (list 'forward 2))
 (make-forward 2)
 "given a list containing a 'forward symbol and a non-negative integer, 
  should return a make-forward")

;; test for a list containing a 'forward symbol and two numbers
(check-equal?
 (decode (list 'forward 2 2))
 #f
 "given a list  containing a 'forward symbol and two numbers, 
  should return false")

;; test for a list containing a 'backward symbol 
(check-equal?
 (decode (list 'backward))
 #f
 "given a list containing a 'backward symbol, 
  should return false")

;; test for a list containing a 'backward symbol and a non-negative integer
(check-equal?
 (decode (list 'backward 2))
 (make-backward 2)
 "given a list containing a 'backward symbol and a non-negative integer, 
  should return a make-backward")

;; test for a list containing a 'backward symbol and two numbers
(check-equal?
 (decode (list 'backward 2 2))
 #f
 "given a list  containing a 'backward symbol and two numbers, 
  should return false")

;; test for a list containing a 'left symbol and a number
(check-equal?
 (decode (list 'left 2))
 #f
 "given a list  containing a 'left symbol and a number, 
  should return false")

;; test for a list containing a 'right symbol and a number
(check-equal?
 (decode (list 'right 2))
 #f
 "given a list containing a 'right symbol and a number, 
  should return false")

;; test for a list containing a 'left symbol
(check-equal?
 (decode (list 'left))
 (make-left)
 "given a list  containing a 'left symbol, 
  should return make-left")

;; test for a list containing a 'right symbol
(check-equal?
 (decode (list 'right))
 (make-right)
 "given a list  containing a 'right symbol, 
  should return make-left")

;; test for a list containing a 'do-times symbol
(check-equal?
 (decode (list 'do-times))
 #f
 "given a list  containing a 'do-times symbol only, 
  should return false")

;; test for a list containing a 'do-times symbol and a number only
(check-equal?
 (decode (list 'do-times 2))
 #f
 "given a list  containing a 'do-times symbol and a number only, 
  should return false")

;; test for a list containing a 'do-times symbol and a valid 
;; left command representation
(check-equal?
 (decode (list 'do-times 2 (list 'left)))
 (make-do-times 2 (make-left))
 "given a list  containing a 'do-times symbol and a valid 
 left command representation, should return make-dotimes")

;; test for a list containing a 'if-at-edge symbol and a number
(check-equal?
 (decode (list 'if-at-ede 2))
 #f
 "given a list containing a 'if-at-edge symbol and a number, 
  should return false")

;; test for a list containing a 'if-at-edge symbol and two valid
;; commands in external syntax
(check-equal?
 (decode (list 'if-at-edge (list 'forward 2) (list 'left)))
 (make-if-at-edge (make-forward 2) (make-left))
 "given a list containing a 'if-at-edge symbol and two valid
  commands in external syntax, should return make-if-at-edge")

;; test for a list containing a 'while-not-edge symbol
(check-equal?
 (decode (list 'while-not-at-edge))
 #f
 "given a list containing a 'while-not-edge, 
  should return false")

;; test for a list containing a 'while-not-edge symbol and a number
(check-equal?
 (decode (list 'while-not-at-edge))
 #f
 "given a list containing a 'while-not-edge, 
  should return false")

;; test for a list containing a 'while-not-edge symbol and a number
(check-equal?
 (decode (list 'while-not-at-edge 2))
 #f
 "given a list containing a 'while-not-edge and a number, 
  should return false")

;; test for a list containing a 'while-not-edge symbol and a valid
;; command in external syntax
(check-equal?
 (decode (list 'while-not-at-edge (list 'forward 2)))
 (make-while-not-at-edge (make-forward 2))
 "given a list containing a 'while-not-edge and a valid
  command in external syntax, should return make-while-not-at-edge")

(check-equal?
(decode (list 'do-times (list (list 'forward 2) (list 'if-at-edge (list 'left) (list 'right)))))
#f
"should return false")

(check-equal?
(decode (list 2 (list 2 (list 'if-at-edge (list 'left) (list 'right)))))
#f
"should return false")

(check-equal?
(decode (cons (cons 'left empty) (cons (cons 2 empty) empty)))
#f
"should return false")

;; interpret : Cmd -> Result
;; takes a command in internal syntax and returns the result after applying actions on
;; the robot
;; Examples: See tests below
;; Strategy: Structural Decomposition [Cmd] with accumulator [res]
(define (interpret cmd0)
  (local  (
           ; interpret-in-context : Cmd Result -> Result
           ; INVARIANT: 
           ; 1. cmd is the n-th sublist of cmd0 where n = length (cmd0 - cmd)
           ; 2. result of (cmd0 - cmd) is in res.
           ; PURPOSE: takes a command in internal syntax and returns the result
           (define (interpret-in-context cmd res)
             (cond 
               [(empty? cmd) res]
               [(struct? cmd) (interpret-unit-command cmd res)]
               [else 
                (interpret-in-context (rest cmd) 
                                      (interpret-unit-command (first cmd) res))])) 
           
           ; interpret-unit-command : UnitCmd Result -> Result
           ; takes an internal unit command and returns the result
           (define (interpret-unit-command cmd res)
             (cond 
               [(forward? cmd) 
                (act cmd res 'forward)]
               [(backward? cmd) 
                (act cmd res 'backward)]
               [(left? cmd) 
                (act cmd res 'left)]
               [(right? cmd)
                (act cmd res 'right)]
               [(do-times? cmd) 
                (exec-n-times cmd res)]
               [(if-at-edge? cmd) 
                (exec-if-at-edge cmd res)]
               [(while-not-at-edge? cmd) 
                (exec-while-not-at-edge cmd res)]))
           
           ; exec-n-times : Do-times Result -> Result
           ; executes the command within do-times command given 
           ; number of times
           (define (exec-n-times cmd res)
             (exec-n-times-helper (do-times-cmd cmd) (do-times-n cmd) res))
           
           ; exec-n-times-helper : Do-times NonNegInt Result -> Result
           ; executes the commands within do-times command given 
           ; number of times
           (define (exec-n-times-helper cmd n res)
             (cond 
               [(zero? n) res]
               [else (exec-n-times-helper cmd (sub1 n) (interpret-in-context cmd res))]))
           
           ; exec-if-at-edge : If-at-edge Result -> Result
           ; executes either command1 or command2 within the if-at-edge command
           ; depending on whether the robot is facing an edge or not respectively
           (define (exec-if-at-edge cmd res)
             (cond 
               [(is-at-edge? res)
                (interpret-in-context (if-at-edge-cmd1 cmd) res)]
               [else (interpret-in-context (if-at-edge-cmd2 cmd) res)]))
           
           ; exec-while-not-at-edge : While-not-at-edge Result -> Result
           ; executes the command within the while-not-at-edge command while the
           ; robot is not facing an edge.
           ; if the robot never faces an edge, the command will keep executing 
           ; infinitely
           (define (exec-while-not-at-edge cmd res)
             (cond
               [(is-at-edge? res) res]
               [else (exec-while-not-at-edge cmd
                                             (interpret-in-context (while-not-at-edge-cmd cmd) res))])))
    (interpret-in-context cmd0 (make-result (list 1 1 'east) empty))))


;; is-at-edge? : Result -> Boolean
;; takes result and checks if the robot is facing the edge, returns true if yes else false
;; Examples : See tests below
;; Strategy : Structural Decomposition [Direction]
(define (is-at-edge? res)
  (cond 
    [(symbol=? (third (result-location res)) 'north) 
     (= (first (result-location res)) 1)]
    [(symbol=? (third (result-location res)) 'south) 
     (= (first (result-location res)) 20)]
    [(symbol=? (third (result-location res)) 'east) 
     (= (second (result-location res)) 20)]
    [(symbol=? (third (result-location res)) 'west) 
     (= (second (result-location res)) 1)]))

;;;;;;;;test for is-at-edge;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(check-equal?
 (is-at-edge? (make-result (list 1 1 'north) (list 'forward)))
 #t
 "when the robot is at edge in north, should return true")

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; move-forward : NonNegInt Result -> Result
;; takes a non-negative integer and result, and returns the updated result 
;; after moving the robot forward by the given number of steps.
;; if the robot might cross an edge, it stops
;; Examples: See tests below
;; Strategy : Structural Decompostion [Result] and [Location]
(define (move-forward n res)
  (move-forward-in-direction (third (result-location res)) 
                             (result-location res) 
                             (result-moves res)
                             n))

;; move-forward-in-direction : Direction Location Moves NonNegInt -> Result
;; takes a direction, location, moves and a non-negative integer, and returns a result 
;; after moving the robot forward by the given number of steps in the given direction.
;; if the robot might cross an edge, it stops
;; Examples: See tests below
;; Strategy : Structural Decompostion [Direction]
(define (move-forward-in-direction dir loc moves n)
  (cond 
    [(symbol=? dir 'north) 
     (move-forward-while-north loc moves n)]
    [(symbol=? dir 'east) 
     (move-forward-while-east loc moves n)]
    [(symbol=? dir 'south) 
     (move-forward-while-south loc moves n)]
    [(symbol=? dir 'west) 
     (move-forward-while-west loc moves n)]))



;; move-forward-while-north : Location Moves NonNegInt -> Result
;; takes a location, moves and a non-negative integer, and returns a result 
;; after moving the robot forward by the given number of steps in the North 
;; direction. If the robot might cross an edge, it stops
;; Examples: See tests below
;; Strategy : Structural Decompostion [Location]
(define (move-forward-while-north loc moves n)
  (make-result (list 
                (- (first loc)
                   (min (sub1 (first loc)) 
                        n))
                (second loc) 'north)
               (append moves 
                       (build-list n (lambda (x) 'forward)))))

;; move-forward-while-east : Location Moves NonNegInt -> Result
;; takes a location, moves and a non-negative integer, and returns a result 
;; after moving the robot forward by the given number of steps in the East 
;; direction. If the robot might cross an edge, it stops
;; Examples: See tests below
;; Strategy : Structural Decompostion [Location]
(define (move-forward-while-east loc moves n)
  (make-result (list (first loc) 
                     (+ (second loc)
                        (min (- 20 (second loc))
                             n)) 'east)
               (append moves 
                       (build-list n (lambda (x) 'forward)))))

;; move-forward-while-south : Location Moves NonNegInt -> Result
;; takes a location, moves and a non-negative integer, and returns a result 
;; after moving the robot forward by the given number of steps in the South 
;; direction. If the robot might cross an edge, it stops
;; Examples: See tests below
;; Strategy : Structural Decompostion [Location]
(define (move-forward-while-south loc moves n)
  (make-result (list (+ (first loc) 
                        (min (- 20 (first loc))
                             n)) 
                     (second loc) 'south)
               (append moves 
                       (build-list n (lambda (x) 'forward)))))

;; move-forward-while-west : Location Moves NonNegInt -> Result
;; takes a location, moves and a non-negative integer, and returns a result 
;; after moving the robot forward by the given number of steps in the West 
;; direction. If the robot might cross an edge, it stops
;; Examples: See tests below
;; Strategy : Structural Decompostion [Location]
(define (move-forward-while-west loc moves n)
  (make-result (list (first loc) 
                     (- (second loc)
                        (min (sub1 (second loc))
                             n)) 'west)
               (append moves 
                       (build-list n (lambda (x) 'forward)))))


;; move-backward : NonNegInt Result -> Result
;; takes a non-negative integer and result, and returns the updated result 
;; after moving the robot backward by the given number of steps.
;; if the robot might cross an edge, it stops
;; Examples: See tests below
;; Strategy : Structural Decompostion [Result] and [Location]
(define (move-backward n res)
  (move-backward-in-direction (third (result-location res)) 
                              res
                              n))


;; move-backward-in-direction : Direction Location Moves NonNegInt -> Result
;; takes a direction, location, moves and a non-negative integer, and returns a result 
;; after moving the robot backward by the given number of steps in the given direction.
;; if the robot might cross an edge, it stops
;; Examples: See tests below
;; Strategy : Structural Decompostion [Direction] 
(define (move-backward-in-direction dir res n)
  (cond 
    [(symbol=? dir 'north) 
     (move-backward-while-north (result-location res) (result-moves res) n)]
    [(symbol=? dir 'east) 
     (move-backward-while-east (result-location res) (result-moves res) n)]
    [(symbol=? dir 'south) 
     (move-backward-while-south (result-location res) (result-moves res) n)]
    [(symbol=? dir 'west) 
     (move-backward-while-west (result-location res) (result-moves res) n)]))

;; move-backward-while-north : Location Moves NonNegInt -> Result
;; takes a location, moves and a non-negative integer, and returns a result 
;; after moving the robot backward by the given number of steps in the North 
;; direction. If the robot might cross an edge, it stops
;; Examples: See tests below
;; Strategy : Structural Decompostion [Location]
(define (move-backward-while-north loc moves n)
  (make-result (list (+ (first loc)
                        (min (- 20 (first loc))
                             n))
                     (second loc) 'north)
               (append moves
                       (build-list n (lambda (x) 'backward)))))

;; move-backward-while-east : Location Moves NonNegInt -> Result
;; takes a location, moves and a non-negative integer, and returns a result 
;; after moving the robot backward by the given number of steps in the East 
;; direction. If the robot might cross an edge, it stops
;; Examples: See tests below
;; Strategy : Structural Decompostion [Location]
(define (move-backward-while-east loc moves n)
  (make-result (list (first loc) 
                     (- (second loc)
                        (min (sub1 (second loc))
                             n)) 'east)
               (append moves 
                       (build-list n (lambda (x) 'backward)))))

;; move-backward-while-south : Location Moves NonNegInt -> Result
;; takes a location, moves and a non-negative integer, and returns a result 
;; after moving the robot backward by the given number of steps in the South 
;; direction. If the robot might cross an edge, it stops
;; Examples: See tests below
;; Strategy : Structural Decompostion [Location]
(define (move-backward-while-south loc moves n)
  (make-result (list (- (first loc) 
                        (min (sub1 (first loc))
                             n)) 
                     (second loc) 'south)
               (append moves 
                       (build-list n (lambda (x) 'backward)))))

;; move-backward-while-west : Location Moves NonNegInt -> Result
;; takes a location, moves and a non-negative integer, and returns a result 
;; after moving the robot backward by the given number of steps in the West 
;; direction. If the robot might cross an edge, it stops
;; Examples: See tests below
;; Strategy : Structural Decompostion [Location]
(define (move-backward-while-west loc moves n)
  (make-result (list (first loc) 
                     (+ (second loc)
                        (min (- 20 (second loc))
                             n)) 'west)
               (append moves 
                       (build-list n (lambda (x) 'backward)))))

;; act : Cmd Result Move : Result
;; takes a command in internal syntax, result and a move. and returns
;; the updated result after applying the given move on the robot
;; Examples: See tests below
;; Strategy: Structural Decomposition [Move] 
(define (act cmd res move)
  (cond
    [(symbol=? move 'forward) (move-forward (forward-n cmd) res)]
    [(symbol=? move 'backward) (move-backward (backward-n cmd) res)]
    [(symbol=? move 'left) (turn-left res)]
    [(symbol=? move 'right) (turn-right res)]))

;; turn-left : Result -> Result
;; takes result and returns the updated result after turning the robot
;; by 90 degrees anti-clockwise
;; Examples: See tests below
;; Strategy: Structural Decomposition [Result] and [Location]
(define (turn-left res)
  (make-result (list (first (result-location res)) 
                     (second (result-location res)) 
                     (change-direction-on-left-turn 
                      (third (result-location res))))
               (append (result-moves res) (list 'left))))

;; turn-right : Result -> Result
;; takes result and returns the updated result after turning the robot
;; by 90 degrees clockwise
;; Examples: See tests below
;; Strategy: Structural Decomposition [Result] and [Location]
(define (turn-right res)
  (make-result (list (first (result-location res)) 
                     (second (result-location res)) 
                     (change-direction-on-right-turn 
                      (third (result-location res))))
               (append (result-moves res) (list 'right))))

;; change-direction-on-left-turn : Direction -> Direction
;; takes a direction and returns the new direction which would be at 90 degrees 
;; anti-clockwise to the given direction
;; Examples: See tests below
;; Strategy: Structural Decomposition [Direction]
(define (change-direction-on-left-turn dir)
  (cond
    [(symbol=? dir 'north) 
     'west]
    [(symbol=? dir 'east) 
     'north]
    [(symbol=? dir 'south) 
     'east]
    [(symbol=? dir 'west) 
     'south]))

;; change-direction-on-right-turn : Direction -> Direction
;; takes a direction and returns the new direction which would be at 90 degrees 
;; clockwise to the given direction
;; Examples: See tests below
;; Strategy: Structural Decomposition [Direction]
(define (change-direction-on-right-turn dir)
  (cond
    [(symbol=? dir 'north) 
     'east]
    [(symbol=? dir 'east) 
     'south]
    [(symbol=? dir 'south) 
     'west]
    [(symbol=? dir 'west) 
     'north]))

;;;;;;;;;;;;;;;;Tests for interpret;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; test for empty Cmd
(check-equal? 
 (interpret empty)
 (make-result (list 1 1 'east) empty)
 "when an empty Cmd is passed, should return the initial state")

;; test for forward Cmd
(check-equal?
 (interpret (make-forward 2))
 (make-result (list 1 3 'east) (list 'forward 'forward))
 "when forward command is given, should return the result with updated location
   and moves")

;; test for backward Cmd at start
(check-equal?
 (interpret (make-backward 2))
 (make-result (list 1 1 'east) (list 'backward 'backward))
 "when backward command is given at the start, should return the result 
   with the initial state")

;; test for backward Cmd after forward Cmd
(check-equal?
 (interpret (list (make-forward 3) (make-backward 1)))
 (make-result (list 1 3 'east) (list 'forward 'forward 'forward 'backward))
 "when backward command is given after forward, should return the updated result 
   with the initial state")

;; test for left Cmd
(check-equal?
 (interpret (make-left))
 (make-result (list 1 1 'north) (list 'left))
 "when left command is given, should return the updated result with changed 
   direction and updated moves")

;; test for right Cmd
(check-equal?
 (interpret (make-right))
 (make-result (list 1 1 'south) (list 'right))
 "when right command is given, should return the updated result with changed 
   direction and updated moves")

(check-equal?
 (interpret (list (make-do-times 3 (make-right))))
 (make-result (list 1 1 'north) (list 'right 'right 'right))
 "given right command is given, should return the updated result with updated 
   direction and moves")

;; test for do-times Cmd
(check-equal?
 (interpret (make-do-times 3 (list (make-forward 2) (make-left) (make-right))))
 (make-result (list 1 7 'east) 
              (list 'forward 'forward 
                    'left 'right 
                    'forward 'forward 
                    'left 'right 
                    'forward 'forward 
                    'left 'right))
 "when do-times command is given, should return the updated result with updated 
   location and moves")

;; test for if-at-edge Cmd
(check-equal?
 (interpret (make-if-at-edge (make-forward 2) (make-left)))
 (make-result (list 1 1 'north) (list 'left))
 "when if-at-edge command is given, should return the updated result with updated 
   location and moves")

;; test for while-not-at-edge Cmd
(check-equal?
 (interpret (make-while-not-at-edge (make-forward 6)))
 (make-result
  (list 1 20 'east)
  (list
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward
   'forward))
 "when while-not-at-edge command is given, should return the updated result with updated 
   location and moves")

;; test for sequence command
(check-equal?
 (interpret (list (make-forward 2) (make-right) (make-backward 1)))
 (make-result (list 1 3 'south) (list 'forward 'forward 'right 'backward))
 "when sequence command is given, the updated result is returned")

;; mixed test
(check-equal?
 (interpret (list (make-do-times 5 (list (make-forward 2) (make-if-at-edge (make-left) (make-right))))))
 (make-result
  (list 5 1 'south)
  (list 'forward 'forward 'right 
        'forward 'forward 'right 
        'forward 'forward 'left 
        'forward 'forward 'right 
        'forward 'forward 'left))
 "given a command is given, should return the updated result with updated 
   location and moves")

(check-equal?
 (move-forward-in-direction 'north (list 1 1 'north) (list 'forward) 1)
 (make-result (list 1 1 'north) (list 'forward 'forward)))

(check-equal?
 (move-backward-while-west (list 1 1 'west) (list 'forward) 1)
 (make-result (list 1 2 'west) (list 'forward 'backward)))

(check-equal?
 (move-backward-in-direction 'north (make-result (list 1 1 'west) (list 'forward)) 1)
 (make-result (list 2 1 'north) (list 'forward 'backward)))

(check-equal?
 (move-backward-in-direction 'west (make-result (list 1 1 'west) (list 'forward)) 1)
 (make-result (list 1 2 'west) (list 'forward 'backward)))
